/*
 * Copyright (c) 2023-2024 elsfs Authors. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.elsfs.cloud.common.util.pinyin;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import lombok.Getter;

@SuppressWarnings("all")
class DoubleArrayTrie {
  private static final int BUF_SIZE = 16384;
  private static final int UNIT_SIZE = 8; // size of int + int
  // boolean no_delete_;
  int error_;
  private int[] check;
  private int[] base;

  private boolean[] used;
  @Getter private int size;
  private int allocSize;
  private List<String> key;
  private int keySize;
  private int[] length;
  private int[] value;
  private int progress;
  private int nextCheckPos;

  public DoubleArrayTrie() {
    check = null;
    base = null;
    used = null;
    size = 0;
    allocSize = 0;
    // no_delete_ = false;
    error_ = 0;
  }

  // int (*progressfunc_) (size_t, size_t);

  // inline _resize expanded
  private int resize(int newSize) {
    int[] base2 = new int[newSize];
    int[] check2 = new int[newSize];
    boolean[] used2 = new boolean[newSize];
    if (allocSize > 0) {
      System.arraycopy(base, 0, base2, 0, allocSize);
      System.arraycopy(check, 0, check2, 0, allocSize);
      System.arraycopy(used2, 0, used2, 0, allocSize);
    }

    base = base2;
    check = check2;
    used = used2;

    return allocSize = newSize;
  }

  private int fetch(Node parent, List<Node> siblings) {
    if (error_ < 0) return 0;

    int prev = 0;

    for (int i = parent.left; i < parent.right; i++) {
      if ((length != null ? length[i] : key.get(i).length()) < parent.depth) continue;

      String tmp = key.get(i);

      int cur = 0;
      if ((length != null ? length[i] : tmp.length()) != parent.depth)
        cur = (int) tmp.charAt(parent.depth) + 1;

      if (prev > cur) {
        error_ = -3;
        return 0;
      }

      if (cur != prev || siblings.isEmpty()) {
        Node tmp_node = new Node();
        tmp_node.depth = parent.depth + 1;
        tmp_node.code = cur;
        tmp_node.left = i;
        if (!siblings.isEmpty()) siblings.get(siblings.size() - 1).right = i;

        siblings.add(tmp_node);
      }

      prev = cur;
    }

    if (!siblings.isEmpty()) siblings.get(siblings.size() - 1).right = parent.right;

    return siblings.size();
  }

  private int insert(List<Node> siblings) {
    // 如果 siblings 为空，直接返回 0 或其他合适的值
    if (error_ < 0 || siblings.isEmpty()) return 0;

    int begin = 0;
    int pos = Math.max(siblings.get(0).code + 1, nextCheckPos) - 1;
    int nonZeroCount = 0;
    boolean isFirstNonZero = true;

    // Ensure initial allocation size is sufficient
    ensureAllocationSize(pos + 1);

    while (true) {
      pos++;

      // Ensure allocation size is sufficient before accessing check[pos]
      ensureAllocationSize(pos + 1);

      if (pos >= allocSize) break; // Prevent infinite loop and array out of bounds

      if (check[pos] != 0) {
        nonZeroCount++;
        continue;
      } else if (isFirstNonZero) {
        nextCheckPos = pos;
        isFirstNonZero = false;
      }

      begin = pos - siblings.get(0).code;
      if (begin + siblings.get(siblings.size() - 1).code >= allocSize) {
        resizeToNextLevel();
      }

      if (used[begin] || !canInsertAt(begin, siblings)) continue;

      break;
    }

    // Adjust nextCheckPos based on density heuristic
    if (1.0 * nonZeroCount / (pos - nextCheckPos + 1) >= 0.95) {
      nextCheckPos = pos;
    }

    used[begin] = true;
    size = Math.max(size, begin + siblings.get(siblings.size() - 1).code + 1);

    updateCheckAndBase(begin, siblings);

    return begin;
  }

  // 辅助方法：确保分配大小足够
  private void ensureAllocationSize(int newSize) {
    if (allocSize <= newSize) {
      resize(newSize);
    }
  }

  // 辅助方法：根据当前分配大小调整到下一个级别
  private void resizeToNextLevel() {
    double factor = Math.max(1.05, 1.0 * keySize / (progress + 1));
    resize((int) (allocSize * factor));
  }

  private boolean canInsertAt(int begin, List<Node> siblings) {
    for (Node sibling : siblings) {
      int index = begin + sibling.code;
      if (index >= allocSize || index < 0 || check[index] != 0) return false;
    }
    return true;
  }

  private void updateCheckAndBase(int begin, List<Node> siblings) {
    for (Node sibling : siblings) {
      int index = begin + sibling.code;
      if (index >= allocSize || index < 0) continue; // Prevent array out of bounds

      check[index] = begin;

      List<Node> newSiblings = new ArrayList<>();
      if (fetch(sibling, newSiblings) == 0) {
        base[index] = (value != null) ? (-value[sibling.left] - 1) : (-sibling.left - 1);
        if (value != null && (-value[sibling.left] - 1) >= 0) {
          error_ = -2;
          return;
        }
        progress++;
      } else {
        int h = insert(newSiblings);
        base[index] = h;
      }
    }
  }

  void clear() {
    // if (! no_delete_)
    check = null;
    base = null;
    used = null;
    allocSize = 0;
    size = 0;
    // no_delete_ = false;
  }

  // no deconstructor

  // set_result omitted
  // the search methods returns (the list of) the value(s) instead
  // of (the list of) the pair(s) of value(s) and length(s)

  // set_array omitted
  // array omitted

  public int getUnitSize() {
    return UNIT_SIZE;
  }

  public int getTotalSize() {
    return size * UNIT_SIZE;
  }

  public int getNonzeroSize() {
    int result = 0;
    for (int i = 0; i < size; i++) if (check[i] != 0) result++;
    return result;
  }

  public int build(List<String> key) {
    return build(key, null, null, key.size());
  }

  public int build(List<String> _key, int[] _length, int[] _value, int _keySize) {
    if (_key == null || _keySize > _key.size()) return 0;

    // progress_func_ = progress_func;
    key = _key;
    length = _length;
    keySize = _keySize;
    value = _value;
    progress = 0;

    resize(65536 * 32);

    base[0] = 1;
    nextCheckPos = 0;

    Node root_node = new Node();
    root_node.left = 0;
    root_node.right = keySize;
    root_node.depth = 0;

    List<Node> siblings = new ArrayList<Node>();
    fetch(root_node, siblings);
    insert(siblings);

    // size += (1 << 8 * 2) + 1; // ???
    // if (size >= allocSize) resize (size);

    used = null;
    key = null;

    return error_;
  }

  public void open(String fileName) throws IOException {
    File file = new File(fileName);
    size = (int) file.length() / UNIT_SIZE;
    check = new int[size];
    base = new int[size];

    try (DataInputStream is =
        new DataInputStream(new BufferedInputStream(new FileInputStream(file), BUF_SIZE))) {
      for (int i = 0; i < size; i++) {
        base[i] = is.readInt();
        check[i] = is.readInt();
      }
    }
  }

  public void save(String fileName) throws IOException {
    try (DataOutputStream out =
        new DataOutputStream(new BufferedOutputStream(new FileOutputStream(fileName)))) {
      for (int i = 0; i < size; i++) {
        out.writeInt(base[i]);
        out.writeInt(check[i]);
      }
    }
  }

  public int exactMatchSearch(String key) {
    return exactMatchSearch(key, 0, 0, 0);
  }

  public int exactMatchSearch(String key, int pos, int len, int nodePos) {
    if (len <= 0) len = key.length();
    if (nodePos <= 0) nodePos = 0;

    int result = -1;

    char[] keyChars = key.toCharArray();

    int b = base[nodePos];
    int p;

    for (int i = pos; i < len; i++) {
      p = b + (int) (keyChars[i]) + 1;
      if (b == check[p]) b = base[p];
      else return result;
    }

    p = b;
    int n = base[p];
    if (b == check[p] && n < 0) {
      result = -n - 1;
    }
    return result;
  }

  public List<Integer> commonPrefixSearch(String key) {
    return commonPrefixSearch(key, 0, 0, 0);
  }

  public List<Integer> commonPrefixSearch(String key, int pos, int len, int nodePos) {
    if (len <= 0) len = key.length();
    if (nodePos <= 0) nodePos = 0;

    List<Integer> result = new ArrayList<Integer>();

    char[] keyChars = key.toCharArray();

    int b = base[nodePos];
    int n;
    int p;

    for (int i = pos; i < len; i++) {
      p = b;
      n = base[p];

      if (b == check[p] && n < 0) {
        result.add(-n - 1);
      }

      p = b + (int) (keyChars[i]) + 1;
      if (b == check[p]) b = base[p];
      else return result;
    }

    p = b;
    n = base[p];

    if (b == check[p] && n < 0) {
      result.add(-n - 1);
    }

    return result;
  }

  // debug
  public void dump() {
    for (int i = 0; i < size; i++) {
      System.err.println("i: " + i + " [" + base[i] + ", " + check[i] + "]");
    }
  }

  private static class Node {
    int code;
    int depth;
    int left;
    int right;
  }
}
